package hot_100;

import java.util.Arrays;

public class 下一个排列 {
    public static void main(String[] args) {

    }

    public void nextPermutation(int[] nums) {
        int n = nums.length;
        for (int i = n - 1; i >= 1; i--) {
            if (nums[i] > nums[i - 1]) {
                int idx = i;
                for (int j = n - 1; j >= i; j--) {
                    if (nums[j] > nums[i - 1]) {
                        idx = j;
                        break;
                    }
                }
                swap(nums, i - 1, idx);
                Arrays.sort(nums, i, n);
                return;
            }
        }
        reverse(nums, 0, n - 1);
    }

    public void reverse(int[] nums, int l, int r) {
        while (r > l) {
            swap(nums, l++, r--);
        }
    }

    public void swap(int nums[], int l, int r) {
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }
}
